/**
 * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，
 * 写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
 * 输入: nums = [-1,0,3,5,9,12], target = 9     
   输出: 4       
   解释: 9 出现在 nums 中并且下标为 4
  输入: nums = [-1,0,3,5,9,12], target = 2     
  输出: -1        
  解释: 2 不存在 nums 中因此返回 -1 
 */

const nums = [1, 2, 4, 6, 9, 12, 22];
//版本一:左闭右闭区间
function twoSearchClose(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  // 左闭右闭区间里应该使用<=
  while (left <= right) {
    let middle = left + Math.floor((right - left) / 2);
    if (arr[middle] > target) {
      right = middle - 1;
    } else if (arr[middle] < target) {
      left = middle + 1;
    } else {
      return middle;
    }
  }
  // 未找到目标值
  return -1;
}
console.log(twoSearchClose(nums, 22)); //6

//版本二:左闭右开区间
function twoSearchOpen(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  // 左闭右开区间,使用<号进行判断
  while (left < right) {
    let middle = left + Math.floor((right - left) / 2);
    if (arr[middle] > target) {
      // 更新右区间,右区间是开区间,所以不要减一
      right = middle;
    } else if (arr[middle] < target) {
      left = middle + 1;
    } else {
      return middle;
    }
  }
  // 没有找到,返回-1;
  return -1;
}

console.log(twoSearchOpen(nums, 22)); //-1
